package main

import (
    "math"
    "io/ioutil"
    "strings"
    "fmt"
    "log"
)

func LCS(A, B []string) [][]int {
    lcs := make([][]int, len(A)+1)
    for i:=0; i<=len(A); i++ {
        lcs[i] = make([]int, len(B)+1)
    }
    for i:=1; i<=len(A); i++ {
        for j:=1; j<=len(B); j++ {
            if A[i-1] == B[j-1] {
                lcs[i][j] = lcs[i-1][j-1] + 1
            } else {
                lcs[i][j] = int(math.Max(float64(lcs[i-1][j]), float64(lcs[i][j-1])))
            }
        }
    }
    return lcs
}

func matchLCS(A, B []string) [][]int {
    lcs := LCS(A, B)
    m, n := len(A), len(B)
    record := make([][]int, 2)
    i, j := m, n
    for i > 0 && j > 0 {
        if A[i-1] == B[j-1] {
            i--
            j--
            record[0] = append(record[0], i)
            record[1] = append(record[1], j)
        } else {
            if lcs[i-1][j] > lcs[i][j-1] {
                i--
            } else {
                j--
            }
        }
    }
    for i:=0; i<len(record[0])/2; i++ {
        record[0][i], record[0][len(record[0])-1-i] = record[0][len(record[0])-1-i], record[0][i]
        record[1][i], record[1][len(record[1])-1-i] = record[1][len(record[1])-1-i], record[1][i]
    }
    return record
}

func Diff(A, B []string) {
    resLCS := matchLCS(A, B)
    if len(resLCS) != 2  || len(resLCS[0]) != len(resLCS[1]) {
        log.Fatal("matchLCS should return 2-D equal size array")
    }
    lenLCS := len(resLCS[0])
    for i:=0; i<lenLCS; i++ {
        if i == 0 {
            if resLCS[0][i] > 0 {  // delete beginning uncommon elements of first array
                fmt.Println(0, resLCS[0][i]-1, "delete\t", A[0:resLCS[0][i]])
            }
            if resLCS[1][i] > 0 {  // add beginning uncommon elements of second array
                fmt.Println(0, resLCS[1][i]-1, " : add\t", B[0:resLCS[1][i]])
            }
        } else {
            if resLCS[0][i-1]+1 < resLCS[0][i] {
                fmt.Println(resLCS[0][i-1]+1, resLCS[0][i]-1, "delte\t", A[resLCS[0][i-1]+1:resLCS[0][i]])
            }
            if resLCS[1][i-1]+1 < resLCS[1][i] {
                fmt.Println(resLCS[1][i-1]+1, resLCS[1][i]-1, "add\t", B[resLCS[1][i-1]+1:resLCS[1][i]])
            }
        }
    }

    if resLCS[0][lenLCS-1] < len(A)-1 {
        fmt.Println(resLCS[0][lenLCS-1]+1, len(A)-1, "delete\t", A[resLCS[0][lenLCS-1]+1:])
    }
    if resLCS[1][lenLCS-1] < len(B)-1 {
        fmt.Println(resLCS[1][lenLCS-1]+1, len(B)-1, "add\t", B[resLCS[1][lenLCS-1]+1:])
    }
}

func DiffFile(file1, file2 string) {
    contents1, err := ioutil.ReadFile(file1)
    if err != nil {
        log.Fatal("error read file")
    }
    A := strings.Split(string(contents1), "\n")
    fmt.Println(A)
    contents2, err := ioutil.ReadFile(file2)
    if err != nil {
        log.Fatal("error read file")
    }
    B := strings.Split(string(contents2), "\n")
    Diff(A, B)
}

func main() {
    DiffFile("reporting_essential.md", "reporting_essential_modified.md")
}
